package binaryTree;

import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;

public class Class297 {
    StringBuilder sb;
    String NULL = "#";
    String SEP=",";
    public String serialize(TreeNode root) {
        sb = new StringBuilder();
        dfs(root);
        return sb.toString();
    }

    //前序遍历　　
    public void dfs(TreeNode root) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        dfs(root.left);
        dfs(root.right);
    }
    // Decodes your encoded data to tree.


//    /* 主函数，将字符串反序列化为二叉树结构 */
//    public TreeNode deserialize(String data) {
////        将字符串转化成列表
//        LinkedList<String > nodes = new LinkedList<>();
//        for (String s : data.split(SEP)) {
//            nodes.addLast(s);
//        }
//        return deserialize(nodes);
//    }
//
//    /* 辅助函数，通过 nodes 列表构造二叉树 */
//    TreeNode deserialize(LinkedList<String> nodes) {
//        if (nodes.isEmpty()) return null;
//        /******前序遍历位置******/
////        列表最左侧就是根节点
//        String first = nodes.removeFirst();
//        if (first.equals(NULL)) return null;
//        TreeNode root = new TreeNode(Integer.parseInt(first));
//        /***********************/
//        root.left = deserialize(nodes);
//        root.right = deserialize(nodes);
//        return root;
//    }

    public TreeNode deserialize(String data) {
        //       将字符串转化成列表
        LinkedList<String > nodes = new LinkedList<>();
        //加入逗号　解决了我的一个疑惑　如何将Ｓｔｒｉｎｇ分割成一个个的字符　　用data.split(SEP)　实现
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    /* 辅助函数，通过 nodes 列表构造二叉树 */
    TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) return null;
        /******前序遍历位置******/
//        列表最左侧就是根节点
        String first = nodes.removeFirst();
        if (first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        /***********************/
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }




    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode2.left = treeNode1;
        treeNode2.right = treeNode3;
        Class297 class297 = new Class297();
        String serialize = class297.serialize(treeNode2);
        System.out.println(serialize);
        TreeNode deserialize = class297.deserialize(serialize);


    }
}
